import collections
from typing import List


class Solution:
    def splitArraySameAverage(self, nums: List[int]) -> bool:
        # 如果只有1个数，则一定无法构成
        if len(nums) == 1:
            return False

        # 如果数组可以直接分成相同的几部分
        count = collections.Counter(nums)
        if all([v % 2 == 0 for v in count.values()]):
            return True
        if all([v % 3 == 0 for v in count.values()]):
            return True
        if all([v % 5 == 0 for v in count.values()]):
            return True
        if all([v % 7 == 0 for v in count.values()]):
            return True
        if all([v % 11 == 0 for v in count.values()]):
            return True
        if all([v % 13 == 0 for v in count.values()]):
            return True

        avg = sum(nums)
        nums = [num * len(nums) - avg for num in nums]

        if 0 in nums:
            return True

        left_nums = [num for num in nums if num < 0]
        high_nums = [num for num in nums if num > 0]

        # print(left_nums, avg, high_nums)

        s1 = len(left_nums)
        low_values = [0 for _ in range(1 << s1)]  # 2**n种可能
        for i in range(s1):
            for j in range(1 << i):
                low_values[(1 << i) + j] = left_nums[i] + low_values[j]

        low_values = set(abs(low) for low in low_values)
        low_values.remove(0)
        low_values.remove(abs(sum(left_nums)))

        s1 = len(high_nums)
        high_values = [0 for _ in range(1 << s1)]  # 2**n种可能
        for i in range(s1):
            for j in range(1 << i):
                high_values[(1 << i) + j] = high_nums[i] + high_values[j]

        high_values = set(high_values)
        high_values.remove(0)
        high_values.remove(sum(high_nums))

        # print(low_values, high_values)

        return len(low_values & high_values) > 0


if __name__ == "__main__":
    print(Solution().splitArraySameAverage([1, 2, 3, 4, 5, 6, 7, 8]))  # True
    print(Solution().splitArraySameAverage([3, 1]))  # False
    print(Solution().splitArraySameAverage([1, 6, 1]))  # False
    print(Solution().splitArraySameAverage([1, 1, 2, 1, 1, 2]))  # True

    # 测试用例58 : True
    print(Solution().splitArraySameAverage([10, 29, 13, 53, 33, 48, 76, 70, 5, 5]))

    # 测试用例59 : False
    print(Solution().splitArraySameAverage(
        [60, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30,
         30, 30]))
